1. Field of the Invention
The present invention relates to a phase unwrapping method and program, and an interference measurement apparatus for obtaining heights from interference fringes of a measurement object, and particularly relates to a phase unwrapping method and program, and an interference measurement apparatus for determining an unwrapping path connecting pixels of phases which are unwrapped from a wrapping phase distribution based on an interference fringe image.
2. Description of the Related Arts
Conventionally, an interference measurement apparatus can measure the surface shape of a sample which is a measurement object with high precision. Therefore, it is utilized in, for example, quality inspection and quality control of various samples such as optical lenses and magnetic disks, semiconductor wafers, MEMS (Micro Electro Mechanical Systems).
FIG. 1 is a conventional interference measurement apparatus using a Michelson-type interference optical system. In FIG. 1, light having strong coherence emitted from a light source 100 is irradiated onto a sample 106 on a piezo-stage 104 and a reference mirror 108 by means of a half mirror 102. The light reflected from the sample 104 and the reference mirror 108 is overlapped again at the half mirror 102, thereby obtaining an interference fringe image. When the light intensity of an interference fringe is I(x,y),
it can be represented by
[Expression 1]I(x,y)=a(x,y)+b(x,y)cos {φ(x,y)}  (1).Herein, a(x,y), b(x,y) are constants determined by the state of the optical system, and φ(x,y) is the phase at the position (x,y) of the interference fringe. Since the phase φ(x,y) and the height h(x,y) of the sample are related with each other according to the following expression (2), the height of the sample can be known by obtaining the phase of the interference fringe.[Expression 2]
                              ϕ          ⁡                      (                          x              ,              y                        )                          =                                            4              ⁢              π                        λ                    ⁢                      h            ⁡                          (                              x                ,                y                            )                                                          (        2        )            
Note that λ is a light source wavelength.
As methods of eliminating influence of a(x,y), b(x,y) from the intensity information of the interference fringe of the expression (1) to obtain the phase φ(x,y) with high precision, for example, a phase shift method, a Fourier transform method, and a heterodyne method are known. However, in these methods, since the phase φ(x,y) is obtained as a function of an arctangent, the phase φ(x,y) is obtained in away that it is folded, i.e., wrapped into −π to π which is the range of the value of the arctangent.
For example, FIG. 2A shows an original phase 110 shown in one dimension wherein the distance is the horizontal axis, and FIG. 2B shows wrapped phases obtained from interference fringes. The process of obtaining a restored phase 114 through restoration from the wrapped phases as shown in FIG. 2B to the original phase as shown in FIG. 2C is called phase unwrapping or, merely, unwrapping.
FIG. 3 shows a phase map (phase distribution) two-dimensionally showing pixels which represent interference fringes, and each of the pixels has an unwrapped phase as pixel data. A phase unwrapping process of, for example, a case in which the phase of a pixel 124 which is at the distal end of an unwrapping path 122 is obtained based on a phase φs of a starting pixel 120 will be described. A restored phase ΦE′ of the pixel 124 can be obtained in the following manner by adding the phase differences from the pixel 120 to the pixel 124.
                              [                      Expression            ⁢                                                  ⁢            3                    ]                ⁢                                  ⁢                              ϕ            E            ′                    =                                    ϕ              S                        +                                          ∑                P                            ⁢                              W                ij                                                                        (        3        )            Herein, φs is a phase at a pixel S, and φE′ is a phase at a pixel E after unwrapping. Moreover, Wij is a phase difference in which phase skip due to wrapping between a pixel i and pixel j which are adjacent to each other along the unwrapping path 122 is corrected. The addition of the expression (3) is performed with respect to all of the adjacent pixels along the unwrapping path 122. In the corrected phase difference Wij of pixels before and after wrapping occurs like a pixel 112-2 and a pixel 112-3 of FIG. 2B, an error of 2π is generated compared with an original phase difference. Generally, in an unwrapping process, interference fringes are assumed to fulfill the Nyquist criterion (at least two or more pixels are sampled for at least one interference fringe frequency). When an interference fringe fulfills the Nyquist criterion, the phase difference between adjacent pixels is always equal to or less than π. Therefore, wrapping is determined to have occurred between pixels where the phase difference between the adjacent pixels is larger than π (or smaller than −π), and the corrected phase difference Wij is calculated as shown in the following expressions by adding −2π (or +2π) to the phase difference.
                              W          ij                =                  {                                                                                          ϕ                    j                                    -                                      ϕ                    i                                                                                                (                                                            -                      π                                        <                                                                  ϕ                        j                                            -                                              ϕ                        i                                                              ≤                    π                                    )                                                                                                                          ϕ                    j                                    -                                      ϕ                    i                                    +                                      2                    ⁢                    π                                                                                                (                                                                                    ϕ                        j                                            -                                              ϕ                        i                                                              ≤                                          -                      π                                                        )                                                                                                                          ϕ                    j                                    -                                      ϕ                    i                                    -                                      2                    ⁢                    π                                                                                                (                                                                                    ϕ                        j                                            -                                              ϕ                        i                                                              >                    π                                    )                                                                                        (        4        )            
When a phase unwrapping process is to be performed according to such expression (3) and expressions (4), if the phase state is sufficiently smooth and continuous in the entire phase map region in FIG. 3, the phase φE′ of the pixel 124 is supposed to be the same value regardless of the unwrapping path. However, in actual measurement, sometimes, the phase is steeply changed in addition to wrapped part due to spatial disturbance of the phase due to the surface state, dust, etc. on the sample, and phase inconsistency (phase non-continuity) is generated when the corrected phase difference is calculated. For example, when the phase difference between a pixel 112-4 and a pixel 112-5 of FIG. 2B is equal to or more than π, and the phase difference between the pixel 112-5 and a pixel 112-6 is equal to or less than π, −2π is added upon calculation of the corrected phase difference between the pixel 112-4 and the pixel 112-5. As shown in the expression (3), the phase difference information of the previous path is added to the phase at the pixel position to be obtained; therefore, once inconsistency of the phase is generated, the error is superimposed on subsequent phases. For example, the error of −2π which is added by mistake at the pixel 112-4 of FIG. 2B affects following phases.
Because of such reason, for example, when simple unwrapping paths 126-1 to 126-9 are set from the starting pixel 120 as shown in FIG. 4, there is a high possibility that the phase unwrapping process fails at paths 126-6 and 126-7 which are present after crossing hatched parts 128-2 and 128-3 where phase non-continuity may occur. As one method of selecting unwrapping paths which is tolerant to such phase non-continuity, the MST method in which a minimum spanning tree (Minimum Spanning Tree) in the phase map is selected as an unwrapping path is known (Authors, P. J. BRYANSTPN-CRPSS et al., Title: Application of the FFT method for the quantitative extraction of information from high-resolution interferometric and photpelastic data, Document Name: Optics & Laser Technology Vol. 26 No 31994; and
Authors, Li An et al., Title: A Fast Implementation of the Minimum Spanning Tree method for Phase Unwrapping, Document Name: IEEE TRANSACTIONS ON MEDICAL IMAGING Vol. 19, NO. 8 AUG. 2000).
The MST method is known as one path problem in graph theory. When the method is utilized in an unwrapping process, as shown in FIG. 5, it is a method which selects, as unwrapping paths, the paths where the values of the magnitude |Wij| of phase differences are added along the paths from the starting pixel 120 is the minimum. Moreover, in order to shorten the processing time of the phase unwrapping which is according to the MST method, a phase unwrapping method in which, when modulation products of interference fringes are out of a predetermined range, they are not stored in a storage list having an ordering function so as to perform path selection is also proposed (JP. 2003-42728).
However, such conventional unwrapping path selection according to the conventional MST method involves a problem that the process in path search takes time. In order to explain this problem, first, an example of simple unwrapping path generating procedures in which the phase difference Wij is not taken into consideration is shown in FIGS. 6A to 6C, and then, they are compared with path selection procedures of FIGS. 7A to 7C according to the MST method.
In FIGS. 6A to 6C, processes up to a third process among entire processes are shown as FIGS. 6A to 6C. In FIGS. 6A to 6C, a queue 130 which is a data structure not having the ordering function is used, and pixel data which is a candidate for determining an unwrapping path is shown in a data format of
candidate pixel i (parent pixel j) and registered, wherein the pixel to be connected to the parent pixel i represents the candidate pixel j. Moreover, white circles of dotted lines are unvisited pixels, solid-line white circles are visited pixels (registered pixels), and black circles represent path-determined pixels. Furthermore, the lines connecting pixels to pixels are called sides, the sides shown by dotted lines represent sides which are currently registered in the queue 130, and the sides shown by solid lines represent the sides which have been determined as unwrapping paths. Hereinafter, details of the procedures will be sequentially described.
(First Procedure)
In a first procedure of FIG. 6A, around an unwrap starting pixel (a), for example, adjacent pixels (d) and (b) are searched in the order of bottom, right, top, and left, and, since they are unvisited pixels, pixel data “d(a)” and “b(a)” is generated and sequentially registered to the queue 130 as candidate pixels. When search of all the adjacent pixels is finished, the candidate pixel (d) which has been stored first among the candidate pixels registered in the queue 130 is retrieved and eliminated, and the side (d→a) connecting the retrieved candidate pixel (d) with the parent pixel (a) thereof is determined as an unwrapping path.
(Second Procedure)
In a second procedure of FIG. 6B, the pixel (d) which has been eliminated from the queue 130 in the first procedure is set as a parent pixel, pixels (g), (e), and (a) which are adjacent around the parent pixel (d) are sequentially searched, the unvisited pixels (g) and (e) are set as candidate pixels, and pixel data “g(d)” and “e(d)” are generated and registered sequentially in the queue 130. When search of all the adjacent pixels is finished, the candidate pixel (b) which has been stored first among the candidate pixels registered in the queue 130 is retrieved and eliminated, and the side (b→a) connecting the retrieved candidate pixel (b) with the parent pixel (a) thereof is determined as an unwrapping path.
(Third Procedure)
In a third procedure of FIG. 6C, the pixel (b) which has been eliminated from the queue 130 in the second procedure is set as a parent pixel, pixels (e), (c), and (a) which are adjacent around the parent pixel (b) are sequentially searched, the unvisited pixel (c) is set as a candidate pixel, and pixel data “c(b)” is generated and registered to the queue 130. When search of all the adjacent pixels is finished, the candidate pixel (g) which has been stored first among the candidate pixels registered in the queue 130 is retrieved and eliminated, and the side (g→d) connecting the retrieved candidate pixel (g) with the parent pixel (d) thereof is determined as an unwrapping path. Thereafter, paths are determined in similar procedures, and the process is finished when there is no more candidate pixel which is to be eliminated from the queue 130. When the unwrapping paths are determined in this manner, the phase differences Wij between the adjacent pixels on the paths are calculated from the expressions (4) and sequentially added according to the expression (3), thereby obtaining an unwrapped phase. In the path search problem of a graph, path search using a queue which is a data structure in which the pixel stored first is prioritized to be retrieved is called breadth-first search. Meanwhile, path search using a stack which is a data structure in which the pixel stored last is prioritized to be retrieved is known as depth-first search. Although such simple path search procedures are high speed, phase difference information is not taken into consideration at all; therefore, when there is non-continuity of phases, the possibility that phase unwrapping thereafter fails is high.
FIGS. 7A to 7C show unwrapping path generating procedures according to the MST method separately in first to third procedures of FIGS. 7A to 7C. In FIGS. 7A to 7C, a heap 132 is used as a data structure used in search of unwrapping paths. In the heap 132, when the candidate pixel j which is adjacent around the parent pixel i is searched, the phase difference Wij is obtained according to the correction calculation of the expressions (4), and data having a format of
candidate pixel j (parent pixel i, weight |Wij|)
is generated and registered as pixel data of the candidate pixel j. Numerical values shown by the sides between the pixels are the phase differences Wij which have undergone the correction calculation, and |Wij| which is the magnitude of the phase differences are used for magnitude determination when they are registered to the heap 132. Herein, in order to simplify the numerical values representing the phase differences, the phase range is standardized to a range of −5 to 5, and these are shown by the numerical values of the sides. The heap 132 is a data structure in which data is retained at nodal points of two trees, and the data of a parent is designed to be smaller than the data of two children, wherein, by using the weight |Wij| for determination of magnitude relations, a candidate pixel having the weight having the minimum value can be always ordered at a root position.(First Procedure)
In a first procedure of FIG. 7A, a starting pixel (a) of phase unwrapping is set as a parent pixel, pixels (d) and (b) which are adjacent around the parent pixel (a) are sequentially searched, the unvisited pixels (d) and (b) are set as candidate pixels so as to generate pixel data of “d(a,2)” and “b(a,5)”,
and the generated candidate pixels are registered to the heap 132, such that the candidate pixel having the minimum weight is disposed at the lowest (root) position of the heap. When search of all the adjacent pixels is finished, the candidate pixel (d) which is registered at the bottom of the heap 132 and has the minimum weight is eliminated from the heap 132, and the side (side d→a) connecting the eliminated candidate pixel (d) with the parent pixel (a) thereof is determined as a phase unwrapping path.(Second Procedure)
In a second procedure of FIG. 7B, the candidate pixel (d) eliminated from the heap 132 in the first procedure is set as a parent pixel, pixels (g), (e), and (a) which are adjacent around the parent pixel (d) are sequentially searched, the unvisited pixels (g) and (e) are set as candidate pixels so as to generate pixel data of “g(d,4)” and “e(d,0)”,
and the generated candidate pixels are registered to the heap 132, thereby ordering them such that the candidate pixel having the minimum weight is at the lowest position of the heap. When search of all the adjacent pixels is finished, the candidate pixel (e) which is registered at the bottom of the heap 132 and has the minimum weight is eliminated from the heap 132, and the side (side e→d) connecting the eliminated candidate pixel (e) with the parent pixel (d) is determined as a phase unwrapping path.(Third Procedure)
In a third procedure of FIG. 7C the candidate pixel (e) which has been eliminated from the heap 132 in the second procedure is set as a parent pixel, and pixels (h), (f), (b), and (d) which are adjacent around the parent pixel (e) are sequentially searched, the unvisited pixels (h), (f), and (b) are set as candidate pixels so as to generate pixel data of
“h(e, 2)”, “(f(e,0)”, and “b(e,3)”,
and they are registered to the heap 132 in the ascending order of the weight of the candidate pixels. However, regarding the candidate pixel (b), the pixel data “b(a,5)” of the same pixel (b) is registered in the heap 132 as shown in FIG. 7B; and, in order to avoid double registration of the same pixel, in this case, the pixel data of the registered candidate pixel (b) is rewritten to the smaller weight “3” and the parent pixel (e) thereof such that “b(e,3)” is set, and the rewritten candidate pixel is registered to the heap 132, thereby ordering them such that the candidate pixel having the minimum weight is at the lowest position of the heap. If the weight of the registered candidate pixel is larger, the same candidate pixel which is newly searched is discarded, and the registered pixel is caused to remain. When search of all the adjacent pixels is finished, the candidate pixel (f) which is registered at the bottom of the heap 132 and has the minimum weight is eliminated from the heap 132, and the side (side f→e) connecting the eliminated candidate pixel (f) with the parent pixel (e) thereof is determined as a phase unwrapping path. Thereafter, paths are determined in similar procedures, and the process is finished when there is no more data of the candidate pixels to be eliminated from the heap 132. When the unwrapping paths are determined in this manner, the unwrapped phases are sequentially obtained according to the expression (3) by use of the phase differences Wij between the adjacent pixels on the paths. In such path search process using the heap 132, the ordering process is performed such that the order of the candidate pixels constitute the heap, wherein the weights which are magnitude of the phase differences of all of the candidate pixels stored in the heap 132 serve as conversion keys; thus, it considerably takes processing time compared with the simple method of FIGS. 6A to 6C in which ordering is not performed. Generally, in the problem of obtaining a minimum spanning tree, since the pixel having the minimum weight, i.e., the pixel at the root position among the pixel data stored in the data structure at the point of time is required to be searched, the time required for ordering the data structure as a heap can be shortened; however, even when a heap is used, minimum rearranging processes of pixel data are required, and, when the number of pixels is increased like an unwrapping phase distribution obtained from interference fringes, the processing time due to the heap cannot be ignored. On the other hand, in Patent Document 3, although a storage list which is different from the heap and has an ordering function is disclosed, the operation of ordering is also generated in this method as well as the heap. Also, in Patent Document 3, when the modulation product of an interference fringe corresponding to the weight which is the phase difference is out of a predetermined range, it is not stored in the storage list having the ordering function so as to perform path selection; however, it is difficult to determine a “predetermined range appropriate for path selection” for a wrapped phase map, and, if normal pixel data is present in a range other than the predetermined range, paths including the normal pixel data out of the range and the paths continued from the pixels following them cannot be obtained. Moreover, Patent Document 3 discloses utilizing, in a region including many noises in the phase map, the storage list which requires ordering, and obtaining unwrapping paths in a region including not many noises through a simpler means; however, even in the region including not many noises, if even one crucial phase non-continuity is present, following phase unwrapping fails. When this point is taken into consideration, all the pixel data having the possibility of noises are desired to be processed in a data structure having an ordering function. In addition, as is clear from the expression (1), the phase at a certain pixel requires the phase difference information in the paths before that. Therefore, when unwrapping paths are obtained independently in respective regions like in Patent Document 3, the phase relation between the regions become inconsistent. In such a case, in order to connect the unwrapping paths which are independent in respective regions, a process for achieving phase matching between the regions is additionally required; thus, separating the unwrapping path selection procedures respectively into the regions is not desirable also in terms of speed-up.